package 双指针;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author TTDB
 * @create 2025/9/13
 */
public class threeSum {
    public List<List<Integer>> threeSum(int[] nums)
    {
        Arrays.sort(nums);
        return nSumTarget(nums, 3, 0, 0);
    }

    // nSumTarget数组，n为i，从哪个下标开始，target为target
    private List<List<Integer>> nSumTarget(int[] nums, int n, int start, int target) {
        int sz = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        if(n < 2 || sz < n) return res;
        if(n == 2){
            int lo = start, hi = sz - 1;
            while(lo < hi){
                int sum = nums[lo] + nums[hi];
                int left = nums[lo], right = nums[hi];
                if(sum < target){
                    while(lo < hi && nums[lo] == left) lo++;
                }else if(sum > target){
                    while(lo < hi && nums[hi] == right) hi--;
                }else{
                    res.add(new ArrayList<>(Arrays.asList(left, right)));
                    while(lo < hi && nums[lo] == left) lo++;
                    while(lo < hi && nums[hi] == right) hi--;
                }
            }
        }else{
            // n > 2 时，递归计算 (n-1)Sum 的结果
            for(int i = start; i < sz; i++){
                //获取 (n-1)Sum 的结果
                List<List<Integer>> sub = nSumTarget(nums, n - 1, i + 1, target - nums[i]);
                // 将 (n-1)Sum 的结果加上 nums[i]
                for(List<Integer> arr : sub){
                    arr.add(nums[i]);
                    res.add(arr);
                }
                // 跳过重复元素
                while(i < sz - 1 && nums[i] == nums[i + 1]) i++;
            }
        }
        return res;
    }
}
